package linkedList

import "fmt"

//单链表
//   实现的功能:
//	1 判断链表是否为空
//   2 单链表的长度
//   3 从头部加入单元素
//   4 尾部加入元素
//   5 指定位置元素
//   6 删除指定元素
//   7 删除指定位置的元素
//   8 查看是否包含某个元素
//   9  遍历/展示所有元素

type Object interface {}

type Node struct{
	Data Object  //数据域
	Next *Node   //定义地址域 ( 指向下一个表的地址)
}

type List struct{
	headNode *Node //头结点
}

// 判断链表是否为空
func (this *List) IsEmpty() bool{
	if this.headNode == nil{
		return true
	}else{
		return false
	}
}

//获取链表长度
func (this *List) Length() int{
	// 第一步, 获取链表的头结点
	cur := this.headNode;
	//定义一个计数器
	count := 0;
	for cur != nil{
		count ++
		cur = cur.Next
	}
	return count
}

//从链表头部添加元素,  然后返回新的链表头部
func (this *List) Add(data Object) *Node{
	node := &Node{ Data: data}
	node.Next = this.headNode
	this.headNode = node;
	return node;
}

// 链表尾部添加元素
func (this *List) Append(data Object){
	node := &Node{Data: data}
	if this.IsEmpty(){
		//如果是空链表, 直接将该元素作为头结点
		this.headNode = node
	}else{
		cur := this.headNode
		//定义变量用于存储头结点
		for cur.Next != nil{
			cur = cur.Next
		}
		cur.Next = node
	}
}

// 链表指定位置添加元素
func (this *List) Insert(index int, data Object){
	if index <0{
		//在链表头部添加元素
		this.Add(data)
	}else if index > this.Length(){
		this.Append(data)
	}else{
		pre :=this.headNode
		count := 0;
		//先查找到指定位置的前一个元素
		for count < (index - 1) {
			pre = pre.Next
			count++
		}
		// 创建新结点
		node := &Node{Data: data}
		node.Next = pre.Next;
		pre.Next = node
	}
}

//删除链表指定值的元素
func (this *List) Remove( data Object){
	pre := this.headNode
	if pre.Data == data{
		// 删除头部元素
		this.headNode = pre.Next
	}else{
		for pre.Next != nil{
			if pre.Next.Data == data{
				//找到了指定元素, pre.Next  指向更靠后的那个元素
				pre.Next = pre.Next.Next
			}else{
				// 如果没找到指定元素
				pre = pre.Next
			}
		}
	}

}

//删除链表指定下标的元素
func (this *List) RemoveByIndex(index int){
	pre := this.headNode
	if index <= 0{
		//移除头结点
		this.headNode = pre.Next
	}else if index > this.Length(){
		fmt.Println("超出链表长度")
		return
	}else{
		//
		count := 0;
		for count != (index -1) && pre.Next != nil{
			count ++
			pre = pre.Next
		}
		pre.Next = pre.Next.Next
	}
}

// 查看链表是否包含某个元素
func (this *List) Contain(data Object) bool {
	cur := this.headNode
	for cur != nil{
		if cur.Data == data {
			return true
		}
		cur = cur.Next
	}
	return false
}


//普通占位符
//占位符     说明                           举例                   输出
//%v      相应值的默认格式。            Printf("%v", people)   {zhangsan}，
//%+v     打印结构体时，会添加字段名     Printf("%+v", people)  {Name:zhangsan}
//%#v     相应值的Go语法表示            Printf("#v", people)   main.Human{Name:"zhangsan"}
//%T      相应值的类型的Go语法表示       Printf("%T", people)   main.Human
//%%      字面上的百分号，并非值的占位符  Printf("%%")
//遍历所有结点
func (this *List) ShowList(){
	if !this.IsEmpty(){
		cur := this.headNode
		for cur != nil{
			fmt.Printf("\t %v", cur.Data)
			cur = cur.Next
		}
	}
}
